import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/5/23
 * Time: 22:00
 */

public class Solution {
    private static int i = 0;
    private static TreeNode createTree(int[] arr) {
        int cur = arr[i];
        TreeNode root = null;
        if(cur != -1) {
            root = new TreeNode(cur);
            i++;
            root.left = createTree(arr);
            root.right = createTree(arr);
        }else {
            i++;
        }
        return root;
    }
    //
    private static TreeNode balanceBST(TreeNode root) {
        List<Integer> array = new ArrayList<>();
        //中序遍历
        inorder(root,array);
        //有序链表构建平衡二叉树
        return buildTree(array,0,array.size() - 1);
    }
    private static void inorder(TreeNode root, List<Integer> array) {
        if(root == null) {
            return;
        }
        inorder(root.left, array);
        array.add(root.val);
        inorder(root.right, array);
    }
    private static TreeNode buildTree(List<Integer> array,int start,int end) {
        if(start > end) {
            return null;
        }
        //中间节点为root
        int mid = start + ((end - start) >> 1);
        TreeNode root = new TreeNode(array.get(mid));
        //递归构造
        root.left = buildTree(array,start,mid - 1);
        root.right = buildTree(array,mid + 1,end);
        //返回
        return root;
    }
    public static void main(String[] args) {
        TreeNode root = createTree(new int[]{1, -1, 2, -1, 3, -1, 4, -1, -1});
        TreeNode treeNode = balanceBST(root);
        System.out.println(treeNode.val);
    }
}